# 设计一个随机的9*9的迷宫，并生成路径
import random
import matplotlib.pyplot as plt
import numpy as np
from collections import deque

# 定义迷宫尺寸
SIZE = 9

# 定义方向常量
UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3


def create_maze(size):
    """创建迷宫"""
    # 初始化迷宫
    maze = [[1] * (size * 2 + 1) for _ in range(size * 2 + 1)]

    # 设置起点
    maze[1][1] = 0

    # 使用DFS算法生成迷宫
    stack = [(1, 1)]
    visited = set([(1, 1)])

    while stack:
        x, y = stack[-1]
        neighbors = []

        # 检查所有可能的方向
        if y > 1 and (x, y - 2) not in visited:
            neighbors.append((x, y - 2, UP))
        if x < size * 2 - 1 and (x + 2, y) not in visited:
            neighbors.append((x + 2, y, RIGHT))
        if y < size * 2 - 1 and (x, y + 2) not in visited:
            neighbors.append((x, y + 2, DOWN))
        if x > 1 and (x - 2, y) not in visited:
            neighbors.append((x - 2, y, LEFT))

        if neighbors:
            nx, ny, direction = random.choice(neighbors)
            visited.add((nx, ny))

            # 打通墙壁
            if direction == UP:
                maze[y - 1][x] = 0
            elif direction == RIGHT:
                maze[y][x + 1] = 0
            elif direction == DOWN:
                maze[y + 1][x] = 0
            elif direction == LEFT:
                maze[y][x - 1] = 0

            maze[ny][nx] = 0
            stack.append((nx, ny))
        else:
            stack.pop()

    return maze


def solve_maze(maze):
    """使用BFS算法寻找迷宫的最短路径"""
    size = (len(maze) - 1) // 2
    start = (1, 1)
    end = (len(maze) - 2, len(maze) - 2)

    # 检查起点和终点是否连通
    if maze[start[0]][start[1]] == 1 or maze[end[0]][end[1]] == 1:
        return None

    queue = deque([start])
    visited = set([start])
    parent = {}

    # 定义四个方向
    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]

    while queue:
        x, y = queue.popleft()

        if (x, y) == end:
            # 重建路径
            path = []
            while (x, y) != start:
                path.append((x, y))
                x, y = parent[(x, y)]
            path.append(start)
            return path[::-1]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze) and maze[ny][nx] == 0 and (nx, ny) not in visited:
                visited.add((nx, ny))
                parent[(nx, ny)] = (x, y)
                queue.append((nx, ny))

    return None


def visualize_maze(maze, path=None):
    """可视化迷宫和路径"""
    maze_array = np.array(maze)

    plt.figure(figsize=(8, 8))
    plt.imshow(maze_array, cmap="binary")

    if path:
        path_x = [point[0] for point in path]
        path_y = [point[1] for point in path]
        plt.plot(path_x, path_y, color="red", linewidth=2, marker="o", markersize=4)

    plt.title("9×9迷宫及其路径")
    plt.xticks([])
    plt.yticks([])
    plt.show()


# 主程序
if __name__ == "__main__":
    # 创建迷宫
    maze = create_maze(SIZE)

    # 解决迷宫
    path = solve_maze(maze)

    if path:
        print("迷宫已生成并找到路径！")
        visualize_maze(maze, path)
    else:
        print("迷宫生成失败或无法找到路径！")